\frame{
	\tableofcontents
}

\section{Comunicação em sigilo e integridade da mensagem}

\frame{
	\frametitle{Comunicação em sigilo e integridade da mensagem}
	\begin{itemize}
                \item Até agora os mecanismos estudados só garantem
                  sigilo.
                  \vfill
		\item Exemplo: Pedido do Supermecado ao fornecedor.
                      \vfill
                      \begin{itemize}
                    
                      \item Foi realmente o supermercado que fez o pedido?
                        \vfill                    
                      \item O pedido é realmente aquele? Ou ocorreu
                        alguma modificação?
                        \vfill       
                      \end{itemize}

       \end{itemize}
}

\section{Cifragem vs. Autenticação da mensagem}

\frame{
	\frametitle{Cifragem vs. Autenticação da mensagem}
	\begin{itemize}
		\item Cifragem, em geral, não provê integridade.
                  \vfill       
                \item Cifragem não resolve imediatamente o problema da
                  integridade da mensagem.
                  \vfill     
                \item Adversário consegui modificar a cifra de forma
                  significativa, mesmo não sabendo o conteúdo da mensagem.
                 \vfill     
                \item Agora mostraremos que os esquemas estudados até agora não provém integridade.
                \vfill     

	\end{itemize}
}

\subsection{Cifragem utilizando cifras de fluxo}

\frame{
	\frametitle{Cifragem utilizando cifras de fluxo}
	\begin{itemize}
		\item $c := G(k) \oplus m$, sendo G um gerador
                  pseudoaleatório.
                  \vfill   
                 \item Imagine que a mensagem cifrada representa uma
                   quantia de dinheiro, caso a cifra seja modificada
                   esta quantia pode ser modificada drasticamente. 
                  \vfill
                  \item Este tipo de ataque não fere a definição de
                    privacidade do esquema dado no
                    capítulo 3.
                   \vfill
                   \item One Time Pad também é suscetível a esse
                     ataque mostrando que até o esquema de sigilo
                     perfeito não garante o nível mais básico de
                     integridade da mensagem.
                    \vfill
	\end{itemize}
}

\subsection{Cifragem utilizando cifras de bloco}

\frame{
	\frametitle{Cifragem utilizando cifras de bloco}
	\begin{itemize}
               \item Trocar um bit no i-ésimo bloco da cifra
                 modificará o i-ésimo bloco da mensagem.  
               \vfill
               \item Em todos os esquemas vistos uma cifra possível
                 corresponde a uma mensagem válida. (Spoof) 
               \vfill
             \item Errata: $m_{1} : = F^{-1}_{k}(c_{1}) \oplus IV'$
	\end{itemize}
 \begin{figure}[!h]
	\centering
	\includegraphics[scale=0.3]{imagens/ecb.png}
	\caption{Electronic Code Book (ECB) mode~\cite{katz}.}\label{ecb}
   \end{figure}
}

\section{Autenticação de mensagens - Definições}

\frame{
	\frametitle{Autenticação de mensagens}
	\begin{itemize}
               \item Objetivo: Detectar se a mensagem foi adulterada.
               \vfill
               \item As partes devem compartilhar um segredo, caso
                 contrário o adversário poderia se passar por alguma
                 das partes.
               \vfill
               \item O esquema criptográfico considerado será o de
                 chave simétrica, aonde as partes compartilham uma
                 chave secreta.
               \vfill
	\end{itemize}
}

\subsection{A sintaxe de um código de autenticação de mensagem}

\frame{
	\frametitle{A sintaxe de um código de autenticação de mensagem}
	\begin{itemize}
               \item Dois usuários os quais desejam se comunicar de
                 uma maneira autenticada, geram e compartilham uma
                 chave secreta $k$.
               \vfill
               \item Quando uma parte deseja enviar uma mensagem $m$,
                 esta calcula uma tag $t$ baseada na mensagem e na
                 chave $k$, $t \leftarrow Mac_{k}(m)$, e então envia a tag junto com a mensagem,$(m,t)$.
              \vfill
               \item A tag é calculada através do algoritmo gerador de
                 tag denotado por Mac.
             \vfill
               \item Ao receber $(m,t)$, o destinatário verifica se a
                 tag $t$ é válida para a mensagem $m$ e a chave
                 $k$. Isto é feito através do algoritmo de verificação Vrfy.
             \vfill
	\end{itemize}
}


\frame{
	\frametitle{Definição formal}
        \begin{block}{Definição}
		Um código de autenticação de mensagem (ou MAC) é uma
                tupla de algoritmos probabilísticos com complexidade polinomial
                (Gen,Mac,Vrfy), tal que:
                \vfill
	      \begin{enumerate}
			\item O algoritmo gerador de chaves Gen recebe
                          como entrada o parâmetro de segurança
                          $1^{n}$ e fornece como saída uma chave $k$ tal
                          que $|k| \geq n$.
                          \vfill
                          \item O algoritmo gerador de tags Mac recebe
                            como entrada a chave $k$ e a mensagem $ m
                            \in \{0,1\}^{*}$ e fornece como saída a tag
                            $t$. Como este algoritmo pode ser
                            aleatório, denotamos esta atribuição
                            $ t \leftarrow $Mac$_{k}(m)$.
                            \vfill
                            \item O algoritmo de verificação Vrfy
                              recebe como entrada a chave $k$, a
                              mensagem $m$ e a tag $t$. E fornece como
                              saída um bit $b$, caso $b = 1$ significa
                              que a tag é válida e $b = 0$ significa
                              que ela é inválida. Assumimos sem perda
                              de generalidade que Vrfy é
                              determinístico, denotado por $b := $Vrfy$_{k}(m,t)$.
                             \vfill
		\end{enumerate}
	\end{block}
}



\frame{
	\frametitle{Definição formal}
	\begin{itemize}
               \item Isto requer que $\forall n, \forall k$ gerado por
                 $Gen(1^{n})$ e $\forall m \in \{0,1\}^{*}$, vale
                 Vrfy$_{k}(m,$Mac$_{k}(m)) = 1$. 
              \vfill
              \item Se (Gen,Mac,Vrfy) é tal que para todo $k$
                fornecido por Gen$(1^{n})$, o algoritmo Mac$_{k}$ só
                está definido para mensagens $m\in\{0,1\}^{l(n)}$ (e
                Vrfy fornece 0 para $\forall m\notin \{0,1\}^{l(n)})$,
                então dizemos que (Gen,Mac,Vrfy) é um MAC de tamanho
                limitado para mensagens de comprimento $l(n)$.  
               \vfill
	\end{itemize}
}

\subsection{Segurança de um código de autenticação de mensagem}
\frame{
	\frametitle{Definição de segurança}
	\begin{itemize}
               \item Nenhum adversário de poder computacional
                 polinomial deve ser capaz de gerar uma tag válida de
                 uma mensagem que não foi anteriormente 
                 autenticada por uma das partes da comunicação. 
               \vfill
               \item Devemos definir o poder do adversário. 
              \vfill
               \item O que constitui uma quebra. 
              \vfill
	\end{itemize}
}

\frame{
	\frametitle{Definição do poder do adversário}
	\begin{itemize}
               \item O adversário pode escutar o canal.
                 \vfill
               \item Pode influenciar o conteúdo das mensagens
                 transmitidas. 
                 \vfill
               \item O adversário possui acesso a um oráculo do
                 algoritmo Mac.
                 \vfill
               \item Dada uma mensagem m, ele tem acesso a sua tag t, $ t \leftarrow $Mac$_{k}(m)$. 
                 \vfill
	\end{itemize}
}

\frame{
	\frametitle{Definição do que constitui uma quebra}
	\begin{itemize}
               \item Caso o adversário seja capaz de fornecer uma
                 mensagem $m$ e uma tag $t$, tal que:
                 \vfill 
                 \begin{itemize}
                 \item Vrfy$_{k}(m,t) = 1$.
                   \vfill 
                 \item A mensagem não foi autenticada anteriormente
                   pelas partes da comunicação e o adversário não requisitou a tag
                  ao oráculo.
                   \vfill
                 \end{itemize}
                 \item Caso o adversário satisfaça a primeira condição
                   o destinatário não consegue diferenciá-lo da outra
                   parte da comunicação. 
                   \vfill
                   \item A segunda condição é necessária pois o
                     adversário sempre pode executar um ataque de replay.
                   \vfill
	\end{itemize}
}


\subsection{Ataques de replay}
\frame{
	\frametitle{Ataques de replay}
	\begin{itemize}
               \item Alice quer transferir para Bob R\$1.000. 
                 \vfill 
               \item Imagine se Bob intercepta a mensagem entre Alice
                 e o Banco e a envia 10 vezes para o Banco. R\$10.000 =) 
                 \vfill 
                 \item Números sequenciais. 
                 \vfill 
                 \item Time-stamp. 
                \vfill 
	\end{itemize}
}

\frame{
	\frametitle{Experimento}
        \begin{block}{Definição}
		Considere o experimento de autenticação de mensagem Mac-forge$_{\mathcal{A},\Pi}(n)$ sobre $\Pi =
                $(Gen,Mac,Vrfy), adversário $\mathcal{A}$ e parâmetro
                de segurança $n$:
                \vfill
	      \begin{enumerate}
			\item Uma chave aleatória $k$ é gerada através
                          de $Gen(1^{n})$. 
                         \vfill 
			\item $\mathcal{A}$ recebe a
                          entrada $1^{n}$ e tem acesso ao oráculo
                          Mac$_{k}(.)$. $\mathcal{A}$ eventualmente
                          fornece como saída um par $(m,t)$. Seja
                          $\mathcal{Q}$ o conjunto de todas as
                          consultas que $\mathcal{A}$ fez ao oráculo.
                         \vfill 
			\item A saída do experimento é 1 se e
                          somente (1) Vrfy$_{k}(m,t)=1$ e (2) $m\notin \mathcal{Q}$ 
                         \vfill 
		\end{enumerate}
	\end{block}
}

\frame{
	\frametitle{Seguro contra este ataque}
        \begin{block}{Definição}
              Um código de autenticação de mensagem $\Pi =
                $(Gen,Mac,Vrfy) é existencialmente inesquecível sobre
                um ataque adaptativo de escolha de mensagem, ou apenas
                seguro, se para todos os adversários de poder
                computacional polinomial  $\mathcal{A}$, existe uma
                função desprezível $negl$ tal que:
              \vfill
	      \begin{enumerate}
			\item Pr[ Mac-forge$_{\mathcal{A},\Pi}(n) = 1
                          $] $\leq negl(n)$.
                         \vfill	 
		\end{enumerate}
	\end{block}
	\begin{itemize}
               \item ``existencialmente inesquecível'' refere-se ao
                 fato do adversário não poder forjar uma tag válida de
                 qualquer mensagem. 
                 \vfill 
               \item ``ataque adaptativo de escolha de mensagem''
                 refere-se ao fato do adversário poder consultar o
                 oráculo de forma adaptativa durante o ataque. 
                 \vfill 
	\end{itemize}

}

\subsection{Esta definição é muito forte?}
\frame{
	\frametitle{Esta definição é muito forte?}
	\begin{itemize}
               \item O adversário pode requesitar a tag de qualquer
                 mensagem, a sua escolha. 
                 \vfill 
               \item É considerada uma quebra se o adversário consegue
                 autenticar uma mensagem não anteriomente autenticada. 
                 \vfill 
                  \item É considerada uma quebra se o adversário consegue
                   autenticar uma mensagem sem significado.
                  \vfill
                  \item Definindo o critério de segurança o mais forte
                    possível garante-se que o protocolo poderá ser
                    utilizado largamente sem se preocupar com compatibilidades.
                  \vfill
	\end{itemize}
}

\section{Construindo códigos seguros de autenticação de mensagem}


\frame{
	\frametitle{Construção}
        \begin{block}{Definição}
              Seja F uma função pseudoaleatória. Definimos um código
              de autenticação de mensagem (MAC) de tamanho fixo $n$ como:
              \vfill
	      \begin{enumerate}
			\item Gen: dada a entrada $1^{n}$, escolhe
                         $k \leftarrow \{0,1\}^{n}$ uniformemente ao acaso.
                         \vfill	 
			\item Mac: dado como entrada a chave $k \in
                          \{0,1\}^{n}$ e a mensagem $m \in
                          \{0,1\}^{n}$, fornece como saída a tag $t :=
                          F_{k}(m)$. (Se $|m|\neq |k|$ então 
                          fornece nada).
                         \vfill	
			\item Vrfy: dado como entrada a chave $k \in
                          \{0,1\}^{n}$, a mensagem $m \in
                          \{0,1\}^{n}$ e a tag $t \in
                          \{0,1\}^{n}$  fornece 1 se e somente se $t \stackrel{?}{=}
                          F_{k}(m)$. (Se $|m|\neq |k|$ então
                          fornece 0).
                         \vfill	  
		\end{enumerate}
	\end{block}
}

\subsection{Teorema MAC de tamanho fixo}
\frame{
	\frametitle{Teorema}
        \begin{block}{Teorema}
            Se F é uma função pseudoaleatória, então a construção
            mostrada anteriormente nos fornece um MAC de tamanho fixo
            para mensagens de tamanho n, o qual é existencialmente
            inesquecível sobre um ataque adaptativo de escolha de
            mensagem, ou seja é seguro! 
          \end{block}
}

\subsection{Prova}
\frame{
	\frametitle{Prova do teorema}
	\begin{itemize}
               \item Esta prova utiliza o mesmo método mostrado no
                 capítulo anterior.
                 \vfill 
               \item Primeiro mostremos que vale para funções
                 realmente aleatórias.
                 \vfill 
               \item Depois considere o resultado obtido trocando a
                 função aleatória para uma pseudoaleatória.
                 \vfill                 
	\end{itemize}
}

\frame{
	\frametitle{Prova do teorema}
	\begin{itemize}
               \item Seja $\mathcal{A}$ um adversário de poder
                 computacional polinomial probabilístico e defina
                 $\varepsilon$ como: $\varepsilon(n)
                 \stackrel{\mathrm{def}}{=}$
                 Pr[Mac-forge$_{\mathcal{A},\Pi}(n) = 1].$
                 \vfill 
               \item Considere um MAC $\widetilde{\Pi} =
                 (\widetilde{\textrm{Gen}},\widetilde{\textrm{Mac}},\widetilde{\textrm{Vrfy}})$
                 igual ao $\Pi =
                 (\textrm{Gen},\textrm{Mac},\textrm{Vrfy})$ exceto pelo fato de utilizar uma
                 função f realmente aleatória invés de usar uma função
                 pseudoaleatória $F_{k}$.
                 \vfill 
                 \item Pr[Mac-forge$_{\mathcal{A},\widetilde{\Pi}}(n)
                   = 1] \leq 2^{-n} $, pois qualquer mensagem $m
                   \notin \mathcal{Q}$, o valor $t=f(m)$ é distribuído
                   uniformemente em $\{0,1\}^{n}$ do ponto de vista do
                   adversário $\mathcal{A}$.
                 \vfill
	\end{itemize}
}

\frame{
	\frametitle{Discriminador D}
        \begin{block}{Definição}
              D recebe a entrada $1^{n}$, tem acesso a um oráculo
              $\mathcal{O}: \{0,1\}^{n} \rightarrow \{0,1\}^{n}$ e
              funciona da seguinte maneira:
              \vfill
	      \begin{enumerate}
			\item Roda $\mathcal{A}(1^{n})$. Sempre que
                          $\mathcal{A}$ consulta o oráculo sobre uma
                          mensagem $m$, responde esta consulta da
                          seguinte maneira: \\ Consulta $\mathcal{O}$
                          com a mensagem m e obtém a resposta $t$;
                          retorna $t$ para $\mathcal{A}$
                        \vfill	  
                        \item Quando $\mathcal{A}$ fornece $(m,t)$ no
                          final da execução, faz:\\
                          (a) Consulta $\mathcal{O}$ com a mensagem
                          $m$ e obtém a resposta $\widetilde{t}  $.\\
                          (b) Se (1) $\widetilde{t} = t$ e (2)
                          $\mathcal{A}$ nunca consultou o oráculo
                          sobre essa mensagem, então fornece 1, caso
                          contrário fornece 0.
                        \vfill
		\end{enumerate}
	\end{block}
}

\frame{
	\frametitle{Final da prova}
	\begin{itemize}
               \item Caso o oráculo de D é uma função pseudoaleatória
                 então D fornece 1 exatamente quando
                 Mac-forge$_{\mathcal{A},\Pi}(n) = 1$, portanto
                 podemos concluir : \\
                 $Pr [D^{F_{k}(.)}(1^{n}) = 1 ] = Pr[ $Mac-forge$_{\mathcal{A},\Pi}(n) = 1
                 ] = \varepsilon(n)$, aonde $k \leftarrow \{0,1\}^{n}$
                 é escolhida uniformemente ao acaso. 
                 \vfill 
              \item Caso o oráculo de D é uma função aleatória
                 então D fornece 1 exatamente quando
                 Mac-forge$_{\mathcal{A},\widetilde{\Pi}}(n) = 1$, portanto: \\
                 $Pr [D^{f(.)}(1^{n}) = 1 ] = Pr[ $Mac-forge$_{\mathcal{A},\widetilde{\Pi}}(n) = 1
                 ]  \leq {1\over{2^{n}}} $, aonde $f \leftarrow$
                 Func$_{n}$
                 é escolhida uniformemente ao acaso. 
                 \vfill 
               \item $|Pr [D^{F_{k}(.)}(1^{n}) = 1 ] - Pr [D^{f(.)}(1^{n}) = 1 ]| \geq
 \varepsilon(n) - {1\over{2^{n}}} $
                 \vfill 
               \item Como F é pseudoaletória existe $\varepsilon(n) -
                 2^{-n} \leq negl(n)$, então $\varepsilon(n)
                 \leq negl(n) + 2^{-n}$ portanto $\varepsilon(n)$ é desprezível.
                 \vfill  
	\end{itemize}
}

\subsection{Extensão para mensagens de tamanho variável}

\frame{
	\frametitle{Extensão para mensagens de tamanho variável}
        \begin{itemize}
              \item A idéia básica é quebrar a mensagem $m$ em blocos
                 $m_{1},..,m_{d}$ e autenticar os blocos.
                 \vfill 
               \item Maneiras erradas de resolver o problema! 
                \vfill
               \item Fazer um XOR de todos os blocos e fazer a
                 autenticação do resultado. Adversário pode modificar
                 uma mensagem autenticada para uma outra mensagem que
                 tenha o mesmo resultado do XOR.
                 \vfill 
               \item Autenticar cada bloco separadamente. Concatenar
                 as tags resultantes. Adversário pode mudar a ordem
                 dos blocos.
                 \vfill 
               \item Autenticar cada bloco com um número
                 sequencial. Adversário pode não transmitir os blocos
                 do final da mensagem. Adversário pode misturar blocos
                 de diferentes mensagens.
                 \vfill  
	\end{itemize}
}

\frame{
	\frametitle{Construção}
        \begin{block}{Definição}
             Seja $\Pi' = $ (Gen',Mac',Vrfy') um MAC de tamanho fixo
             para mensagens de tamanho $n$. Definimos um MAC de
             tamanho variável como:
              \vfill
	      \begin{enumerate}
			\item Gen: idêntico a Gen'.
                        \vfill	  
			\item Mac: dado a chave $k \in
                          \{0,1\}^{n}$ e a mensagem $m \in
                          \{0,1\}^{*}$ de tamanho $l <
                          2^{{n\over{4} } }$, divida $m$ em $d$ blocos
                            $m_{1},...,m_{d}$ cada um de tamanho
                            ${n\over{4}}$. (O último bloco é
                              preenchido com zero caso
                              necessário). Após isto escolhe-se um
                              identificador aleatório $r \leftarrow
                              \{0,1\}^{{n\over{4}}} $\\
                                Para $i=1,...,d$, compute $t_{i}
                                \leftarrow
                                $Mac$_{k}'(r||l||i||m_{i})$, onde $i$
                                e $l$ são unicamente codificados como
                                strings de tamanho $n/4$. Finalmente,
                                fornece a tag $t:=<r,t_{1},...,t_{d}>$.
                        \vfill
			\item Vrfy: dada a chave $k \in
                          \{0,1\}^{n}$, a mensagem $m \in
                          \{0,1\}^{*}$ de tamanho $l<2^{{n\over{4}}}$ e a tag $t=<r,t_{1},...,t_{d}>$,divide $m$ em $d$ blocos
                            $m_{1},...,m_{d}$ cada um de tamanho ${n\over{4}}$. (O último bloco é
                              preenchido com zero caso
                              necessário). Fornece 1 se e somente se
                              $d'=d$ e
                              Vrfy$_{k}'(r||l||i||m_{i},t_{i}) = 1$
                              para $1 \leq i \leq d$.
                         \vfill  
		\end{enumerate}
	\end{block}
}

\subsection{Teorema MAC de tamanho varíavel}
\frame{
	\frametitle{Teorema}
        \begin{block}{Teorema}
          Se $\Pi'$ é um MAC seguro de tamanho fixo para mensagens de
          tamanho $n$, então a construção anterior é um MAC
          existencialmente inesquecível sobre um ataque adaptativo de
          escolha de mensagem, ou seja é seguro!   
          \end{block}
}


\subsection{Prova}
\frame{
	\frametitle{Prova do teorema}
	\begin{itemize}
               \item A intuição é que se $\Pi'$ é seguro um adversário
                 não consegue introduzir um novo bloco com uma tag válida.
                 \vfill                
                 \item Seja $\Pi$ o MAC dado pela construção
                   anterior. Seja $\mathcal{A}$ um adversário de poder
                   computacional polinomial probalístico e defina
                   $\varepsilon$ como: $\varepsilon(n)
                 \stackrel{\mathrm{def}}{=}
                 \textrm{Pr}[\textrm{Mac-forge}_{\mathcal{A},\Pi}(n) = 1].$
                  \vfill
                  \item Seja Repetição o evento em que o mesmo
                    identificador de mensagem aparece em duas tags
                    retornadas pelo oráculo no experimento. 
                  \vfill
                  \item Seja Forjar o evento em que $\mathcal{A}$ é
                    capaz de produzir uma tag válida de uma mensagem
                    não previamente autenticada pelo MAC $\Pi'$ de
                    tamanho fixo.
                  \vfill
	\end{itemize}
}

\frame{
	\frametitle{Prova do teorema}
       (Eq 4.3) $\textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n) = 1] = 
        \textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n) = 1 $ e $\textrm{Repeat}] $\\
       \begin{flushright} $+
         \textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n) = 1  $ e $
         \overline{\textrm{Repeat}} $ e $ \overline{\textrm{Forge}} ]$\\ \end{flushright}
      \begin{flushright} $+ \textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n)
        = 1   $ e $
         \overline{\textrm{Repeat}}$ e $\textrm{Forge}]$. \end{flushright}
                 \vfill 
	\begin{itemize}
               \item Mostraremos que
                 $\textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n) = 1 $ e $\textrm{Repeat}]
                 \leq \textrm{Pr[Repeat}]$ é desprezível.
                 \vfill 
               \item E que $\textrm{Pr[Mac-forge}_{\mathcal{A},\Pi}(n) = 1$  e
        $ \overline{\textrm{Repeat}} $ e $\overline{\textrm{Forge}}] = 0$\\ 
                \vfill 
	\end{itemize}
}

\frame{
	\frametitle{O problema do aniversário}
	\begin{itemize}
               \item Qual é o tamanho de um grupo de pessoas para se
                 ter certeza com probabilidade 1/2 que duas pessoas
                 fazem aniversário no mesmo dia do ano?  
                 \vfill 
               \item São necessárias 23 pessoas. 
                 \vfill 
                 \item Lema A.9 limite superior, Lema A.10 limite
                   inferior. 
                 \vfill
               \item Lema A.9: Fixando um inteiro positivo N e q elementos $y_{1},...,y_{q}$
                 escolhidos de forma uniforme e independente ao acaso
                 de um conjunto de tamanho N. Então a probabilidade de
                 existirem $i$,$j$ distintos tais que $y_{i}=y_{j}$ é
                 no máximo ${q^{2}\over{2N}}$. 
                 \vfill 
               \item Isto é $coll(q,N) \leq {q^{2}\over{2N}}$
                 \vfill  
	\end{itemize}
}

\frame{
	\frametitle{Afirmação 4.7}
	\begin{itemize}
               \item Existe uma função desprezível tal que $Pr[Repeat]
                 \leq negl(n)$. 
                 \vfill 
               \item Seja q(n) a quantidade de consultas ao oráculo.
                 \vfill 
               \item $r_{i} \leftarrow \{0,1\}^{ n\over{4} }$ então $N
                 = |\{0,1\}^{ n\over{4} }| = 2^{ n\over{4} }$
                 \vfill 
               \item Pr[Repeat] $\leq {q(n)^{2}\over{2*2^{ n\over{4} } }}$
               $  \leq { {q(n)^{2}} \over {2^{{n\over{4}}} } } $
                 \vfill  
              \item Como a quantidade de consultas é polinomial então
                esta função é desprezível, provando a afirmação. 
               \vfill  
	\end{itemize}
}

\frame{
	\frametitle{Afirmação 4.8}
	\begin{itemize}
               \item Pr[Mac-forge$_{\mathcal{A},\Pi}(n) = 1$  e $
                 \overline{Repeat} $ e $\overline{Forge}] = 0$. 
                 \vfill 
                 \item Seja Mac-forge$_{\mathcal{A},\Pi}(n) = 1$ e o
                   evento Repetição não ocorre, mostraremos que
                   necessariamente o evento Forjar tem que ocorrer.
                 \vfill
                \item 1) O identificador $r$ é diferente de todos os
                   usados pelo oráculo. Como $\mathcal{A}$ obteve
                   sucesso no ataque então ocorreu o evento Forjar. 
                 \vfill
                \item 3) O identificador $r$ foi usado mais de uma vez
                 pelas tags obtidas através do oráculo. Isto não pode
                 ocorrer pois o evento de Repetição não ocorre. 
                 \vfill 
              
	\end{itemize}
}

\frame{
	\frametitle{Afirmação 4.8}
	\begin{itemize}
               \item 2) O identificador $r$ foi usado exatamente uma vez
                 por uma tag obtida pelo $\mathcal{A}$ através do oráculo:
                 Denote por $m$' a mensagem que o $\mathcal{A}$
                 consultou o oráculo para qual a resposta $t$'
                 continha o identificador $r$. Como $m \notin
                 \mathcal{Q}$ nós temos que $m \neq m'$. 
                 Seja $l'$ o tamanho da mensagem $m$'. Então existem dois subcasos:
                 \vfill 
               \item (a) $l' \neq l$. Neste caso a tag $r||l||1||m_{1}$
                 não foi autenticada anteriormente pelo oráculo.Todas
                 as consultas ao oráculo utilizam um tamanho diferente
                 da mensagem $m$. Como $\mathcal{A}$ obteve
                   sucesso no ataque então ocorreu o evento Forjar.  
                 \vfill 
               \item (b) $l' = l$. Mesma quantidade de blocos, porém
                 diferem em pelo menos um bloco pois senão seriam a
                 mesma mensagem. Neste bloco i a tag
                 $r||l||i||m_{i}$ não foi anteriormente autenticada
                 pelo oráculo.  Como $\mathcal{A}$ obteve
                   sucesso no ataque então ocorreu o evento Forjar.
                 \vfill  
	\end{itemize}
}

\frame{
	\frametitle{Prova}
	\begin{itemize}
               \item Retornando a equação 4.3 e utilizando as duas
                 afirmações posteriores, temos: \\
                 Pr[Mac-forge$_{\mathcal{A},\Pi}(n) = 1  $ e $
                 \overline{Repeat}$ e Forge] $\geq \varepsilon(n) - negl(n)$.
                 \vfill 
               \item Considere um Adversário $\mathcal{A}'$ com poder
                 computacional polinomial probabilístico o qual ataca
                 um MAC $\Pi$' de tamanho fixo e obtém sucesso ao
                 forjar.
                 \vfill 
                 \item Assim $\mathcal{A}'$ utiliza  $\mathcal{A}$
                   como subrotina. 
                 \vfill
	\end{itemize}
}

\frame{
	\frametitle{}
	\begin{itemize}
               \item A visão de $\mathcal{A}$ quando rodado como
                 subrotina de $\mathcal{A}'$ é a mesma visão de
                 $\mathcal{A}$ no experimento
                 Mac-forge$_{\mathcal{A},\Pi}(n)$, portanto:
                 \vfill 
               \item  Pr[Mac-forge$_{\mathcal{A}',\Pi'}(n) = 1] =$
                 Pr[Mac-forge$_{\mathcal{A},\Pi}(n) = 1$ e Forge] \\
               \begin{flushright}  $\geq$ Pr[Mac-forge$_{\mathcal{A},\Pi}(n) = 1$ e $\overline{Repeat}$ e Forge]\\\end{flushright}
                \begin{center} $\geq  \varepsilon(n) - negl(n)$\end{center}
                 \vfill  
                \item Pela segurança de $\Pi$', sabemos que
                  Pr[Mac-forge$_{\mathcal{A}',\Pi'}(n) = 1]$ tem que ser
                  desprezível. Isto implica que $\varepsilon(n)$
                  também é desprezível. 
                 \vfill 
	\end{itemize}
}
